package a00_LeetCode.Tree;

import sun.reflect.generics.tree.Tree;

/**
 * @Author quan
 * @Description 将二叉树展开为链表
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 * @Date 2023/4/2 16:45
 */
public class Num114_flatten {
    /**
     * 思路：对于一个节点 x，可以执行以下流程：     *
     * 1、先利用 flatten(x.left) 和 flatten(x.right) 将 x 的左右子树拉平。     *
     * 2、将 x 的右子树接到左子树下方，然后将整个左子树作为右子树。
     */
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        //先把左右子树拉平
        flatten(root.left);//左
        flatten(root.right);//右
        //**********后序遍历的位置**********
        //此时左右子树已经被拉平成一条链表，单独记录下来
        TreeNode left = root.left;
        TreeNode right = root.right;
        //将左子树作为右子树
        root.left = null;
        root.right = left;
        //遍历此时的树，一直走到树为空的地方，将先前的右子树拼接到末端
        TreeNode p = root;
        while (p.right!=null){
            p = p.right;
        }
        p.right = right;
    }
}
